export const quickSort = (arr) => {
    sort(arr, 0, arr.length - 1)
    return arr
}

const sort = (arr, l, r) => {
    if (l >= r) {
        return
    }

    const p = partition(arr, l, r)
    sort(arr, l, p - 1)
    sort(arr, p + 1, r)
}

const partition = (arr, l, r) => {
    let j = l

    for (let i = l; i <= r; i++) {
        if (arr[i] < arr[l]) {
            j++
            swap(arr, i, j)
        }
    }
    swap(arr, l, j)
    return j
}

const swap = (arr, i, j) => {
    const tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
}

export const quickSort2 = (arr) => {
    const copyArr = [...arr]

    if (copyArr.length <= 1) {
        return copyArr
    }

    const pivot = copyArr.shift()
    const smallerArr = []
    const biggerArr = []
    const centerArr = [pivot]

    while (copyArr.length) {
        const current = copyArr.shift()

        if (current == pivot) {
            centerArr.push(current)

        } else if (current < pivot) {
            smallerArr.push(current)

        } else if (current > pivot) {
            biggerArr.push(current)

        }
    }

    const smallerSortedArr = quickSort2(smallerArr)
    const biggerSortedArr = quickSort2(biggerArr)

    return smallerSortedArr.concat(centerArr, biggerSortedArr)
}